package week02

// 30. 串联所有单词的子串
// https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

func findSubstring(s string, words []string) []int {
	var count = calcWord(words)

	var ans []int
	var length = len(words[0])
	for i := 0; i+len(words)*length <= len(s); i++ {
		// 子串的长度 = words中所有单词长度加起来
		if check(s[i:i+len(words)*length], length, count) {
			ans = append(ans, i)
		}
		// 不能滑动一个单词的长度
		// "aaaaaaaaaaaaaa"
		// ["aa","aa"]
	}

	return ans
}

// 统计每个单词数量
func calcWord(words []string) map[string]int {
	var count = make(map[string]int)
	for _, word := range words {
		count[word]++
	}
	return count
}

func check(str string, wordLen int, count map[string]int) bool {
	var calc = make(map[string]int)
	for i := 0; i+wordLen <= len(str); i+=wordLen {
		var sub = str[i:i+wordLen]
		if _, ok := count[sub]; ok {
			calc[sub]++
		} else {
			return false
		}
	}
	return equals(calc, count)
}

func equals(a, b map[string]int) bool {
	if len(a) != len(b) {
		return false
	}
	for k, v := range a {
		if v1, ok := b[k]; !ok || v != v1 {
			return false
		}
	}
	return true
}